package com.swak.algs;

import java.util.Arrays;

import com.swak.algs.array.Prints;
import com.swak.algs.array.Swaps;
import com.swak.algs.sample.Samples;

/**
 * 选择排序：选择一个数据和指定位置的交换
 * 
 * @author lifeng
 */
public class Code02 {

	static void print(int arr[]) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	/**
	 * 标准的流程
	 * 
	 * @param arr
	 */
	static void selectSort(int arr[]) {

		/*
		 * 边界的判断
		 */
		if (arr == null || arr.length < 2) {
			return;
		}

		/*
		 * 找到长度
		 */
		int N = arr.length;

		/*
		 * 0   ~  N-1 
		 * 1   ~  N-1 
		 * N-2 ~  N-1 最后一位不需要和自己比较
		 * 
		 * 注意这里的变化部分数开始的数
		 */
		for (int i = 0; i <= N - 1; i++) {
			int n = i;
			for (int j = i + 1; j <= N - 1; j++) {
				n = arr[n] > arr[j] ? j : n;
			}
			Swaps.swap(arr, i, n);
		}
	}

	/**
	 * 选择排序1
	 * 
	 * @param arr
	 */
	static void sort1(int arr[]) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = 0; i <= arr.length - 1; i++) {
			int n = i;
			for (int j = i + 1; j <= arr.length - 1; j++) {
				if (arr[n] > arr[j]) {
					n = j;
				}
			}
			Swaps.swap(arr, i, n);
		}
	}

	public static void main(String[] args) {
		Prints.print(Samples.randomSample(10, 10));
		Samples.randomSampleTest(100, 100, 500000, (ans) -> Arrays.sort(ans), (ans) -> sort1(ans),
				(ans) -> selectSort(ans));
	}
}
